
test0 = """Hello\nI am Edwin\nGood Morning."""
test1 = """Great\nHello\nI am Xingjing\nGood Morning!"""
test2 = """Hello\nGreat\n\nI am Edwin Lee\nGood Morning!!!"""

def _mergeDiff(di):
    dii = iter(di)
    a = dii.next()
    opt, res = a[0], a[2:]
    c = 1
    for i in di:
        opt1, text = i[0], i[2:]
        if opt1 == "?": continue
        if opt1 == opt:
            res += text
            c += 1
        else:
            if opt==" ": yield c
            elif opt=="+": yield (res);
            else: yield -c
            res, opt = text, opt1
            c = 1
    if opt==" ": yield c
    elif opt=="+": yield (res)
    else: yield -c

def _getDiff(di):
    return list(_mergeDiff(di))

def getDiff(src, tgt):
    import difflib
    di = difflib.ndiff(src, tgt)
    return _getDiff(di)

def recover(src, diffs):
    temi = iter(src)
    for i in diffs:
        if type(i) == type(""):
            yield i
            continue
        opt = int(i)
        if opt<0:
            for j in xrange(-opt): temi.next()
        else:
            for j in xrange(opt): yield temi.next()    
    

class DiffObj(object):
    """
    >>> a = DiffObj(test0, test1)
    >>> a.recoverTgt() == test1
    True
    >>> b = a.diff(test2)
    >>> a.recoverTgt() == test2
    True
    """
    def __init__(self, tem, tgt=None):
        self.tem = tem
        if tgt!=None: self.diff(tgt)
    def diff(self, tgt):
        self.diffs = getDiff(self.tem, tgt)
        return self.diffs
    def recoverTgt(self):
        return "".join(recover(self.tem, self.diffs))

def _split(astr, splitchar):
    s = ""
    ans = []
    for i in astr:
        if i != splitchar: s += i
        else: ans.append(s+splitchar); s = ""
    if s != "": ans.append(s)
    return ans

class DiffObjLine(DiffObj):
    """
    >>> a = DiffObjLine(test0, test1)
    >>> a.recoverTgt() == test1
    True
    >>> b = a.diff(test2)
    >>> a.recoverTgt() == test2
    True
    """    
    def __init__(self, tem, tgt=None, splitchar="\n"):
        self.splitchar = splitchar
        super(DiffObjLine, self).__init__(_split(tem, splitchar), tgt)
    def diff(self, tgt):
        tgt = _split(tgt, self.splitchar)
        super(DiffObjLine, self).diff(tgt)

def compress(src, tgt, splitchar=None):
    """
    >>> def test(a, b): return decompress(a, compress(a, b))==b
    >>> t = [test0, test1, test2]
    >>> all([test(i, j) for i in t for j in t])
    True
    """
    if splitchar==None: return str(getDiff(src, tgt))
    else: return str(getDiff(_split(src, splitchar), _split(tgt, splitchar)))

def decompress(src, delta_str):
    return "".join(recover(src, eval(delta_str)))

if __name__=="__main__":
    a = DiffObjLine(test0, test2)
    print a.diffs
    print "-" * 18
    print a.recoverTgt()
    import doctest
    doctest.testmod()
